{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Re-Space LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #hash-table #string #dynamic-programming #hash-function #rolling-hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #哈希表 #字符串 #动态规划 #哈希函数 #滚动哈希"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: respace"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #恢复空格"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子<code>&quot;I reset the computer. It still didn&rsquo;t boot!&quot;</code>已经变成了<code>&quot;iresetthecomputeritstilldidntboot&quot;</code>。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典<code>dictionary</code>，不过，有些词没在词典里。假设文章用<code>sentence</code>表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题相对原题稍作改动，只需返回未识别的字符数</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>\n",
    "dictionary = [&quot;looked&quot;,&quot;just&quot;,&quot;like&quot;,&quot;her&quot;,&quot;brother&quot;]\n",
    "sentence = &quot;jesslookedjustliketimherbrother&quot;\n",
    "<strong>输出：</strong> 7\n",
    "<strong>解释：</strong> 断句后为&quot;<strong>jess</strong> looked just like <strong>tim</strong> her brother&quot;，共7个未识别字符。\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= len(sentence) &lt;= 1000</code></li>\n",
    "\t<li><code>dictionary</code>中总字符数不超过 150000。</li>\n",
    "\t<li>你可以认为<code>dictionary</code>和<code>sentence</code>中只包含小写字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [re-space-lcci](https://leetcode.cn/problems/re-space-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [re-space-lcci](https://leetcode.cn/problems/re-space-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"looked\",\"just\",\"like\",\"her\",\"brother\"]\\n\"jesslookedjustliketimherbrother\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        \"\"\"\n",
    "        动态规划\n",
    "        状态定义：dp[i]，0 <= i <= len(sentence)\n",
    "            集合：前 i 个字符所有可能的划分方式\n",
    "            属性：Min(未识别的字符数)\n",
    "        状态转移：\n",
    "            集合划分：\n",
    "                第 i 个字符无法与前面任何一个子串组成单词：dp[i - 1] + 1\n",
    "                第 i 个字符可以与前面某个子串组成单词：dp[j]\n",
    "                if sentence[j:i] in dictionary，0 <= j <= i - 1\n",
    "            初始化：dp[0] = 0，当 sentence 为空字符串时，未识别字符数为 0\n",
    "            答案：dp[-1]\n",
    "        \"\"\"\n",
    "        # 动态规划\n",
    "        d = set([x for x in dictionary if x in sentence])  # 筛选存在sentence中的单词并哈希化\n",
    "        n = len(sentence)\n",
    "        dp = [n for _ in range(n+1)]  # 动态规划数组初始化\n",
    "        dp[0] = 0  # 初始变量0\n",
    "        for i in range(n+1):\n",
    "            # 找得到的就保留未识别字符的最小值（即比上一个加一要少），找不到就+1后移\n",
    "            dp[i] = min(dp[i], dp[i-1]+1)  # 当前dp[i]赋值\n",
    "            for x in d:  # 遍历字典单词 \n",
    "                j = i + len(x)\n",
    "                if sentence[i:j] == x:\n",
    "                    dp[j] = min(dp[i], dp[j])  # 对dp[j] 赋值\n",
    "        return dp[-1]  # 输出最后一个的未识别字符\n",
    "\n",
    "\n",
    "        # 动态规划\n",
    "        dictionary = set(dictionary)\n",
    "        n = len(sentence)\n",
    "        dp = [0] + [n for _ in range(n)]  # 动态规划变量 - 最少未识别字符数\n",
    "        for j in range(1, n+1):  # 1~n\n",
    "            for i in range(j):  # 0~j\n",
    "                if sentence[i:j] in dictionary:\n",
    "                    dp[j] = min(dp[j], dp[i])  # \n",
    "                else:\n",
    "                    dp[j] = min(dp[j], dp[i]+j-i)  # 状态转移方程\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        ll = len(sentence)\n",
    "        dp = [0]*(ll+1)\n",
    "        ld = len(dictionary)\n",
    "        for i in range(1,ll+1):\n",
    "            dp[i] = dp[i-1]+1\n",
    "            for j in range(ld):\n",
    "                lw = len(dictionary[j])\n",
    "                if lw<=i and sentence[i-lw:i]==dictionary[j]:\n",
    "                    dp[i] = min(dp[i],dp[i-lw])\n",
    "        return dp[ll]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        s = set(dictionary)\n",
    "        n = len(sentence)\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            f[i] = f[i-1]\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in s:\n",
    "                    f[i] = max(f[i], f[j] + i-j)\n",
    "        return n - f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        # 动态规划\n",
    "        dictionary = set(dictionary)\n",
    "        n = len(sentence)\n",
    "        dp = [0] + [n for _ in range(n)]  # 动态规划变量 - 最少未识别字符数\n",
    "        for j in range(1, n+1):\n",
    "            for i in range(j):\n",
    "                if sentence[i:j] in dictionary:\n",
    "                    dp[j] = min(dp[j], dp[i])\n",
    "                else:\n",
    "                    dp[j] = min(dp[j], dp[i]+j-i)\n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "\n",
    "        dictionary = set(dictionary) # 1\n",
    "        n = len(sentence)\n",
    "        dp = [0] * (n + 1) #2.c\n",
    "        for i in range(n + 1): #2.a\n",
    "            dp[i] = dp[i - 1] + 1 #2.d\n",
    "            for j in range(i + 1): #2.a, 2.b\n",
    "                if sentence[j: i] in dictionary: # 2.e\n",
    "                    dp[i] = min(dp[i], dp[j]) \n",
    "        return dp[-1] - 1 #2.f\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# dictionary = [\"looked\",\"just\",\"like\",\"her\",\"brother\"]\n",
    "# sentence = \"jesslookedjustliketimherbrother\"\n",
    "\n",
    "# a.遍历的顺序：第一层遍历从sentence的第一个字母遍历到最后一个字母。这次遍历代表的是每个可能的单词的最后一个字母所在的位置（i）\n",
    "\n",
    "# 。第二层遍历从最后一个字母所在的位子往前遍历到sentence的第一个字母。这次遍历表示的是可能的单词第一个字母所在的位置（j）。\n",
    "\n",
    "\n",
    "# 通过这两层遍历，i与j中间的所框定的内容就表示的是若以该字母为某个单词的最后一个字母，所有可能的单词的情况。 \n",
    "\n",
    "\n",
    "# b. 特别的，字典中可能存在单个字母所构成的单词的情况。所以j的遍历要到i所对应的元素为止。确保一个字母构成的单词也可能出现。 \n",
    "\n",
    "# c. 构建一个list来储存动态规划中对每个元素而言，其之前的内容中不在字典内的字符的个数。\n",
    "\n",
    "#  d. 如果字典为空，那么dp指针从左往右的过程中,每次向右移动就加上一个新的字符。 \n",
    " \n",
    "#  e. 考虑字典不为空，那么如果出现了字典的内容，那么对应单词的最后一个字母的位置就应该剔除掉之前因为误以为该单词不在字典中而错误累加的个数（误加了单词的长度的个数）。换言之，单词的最后一个字母的位置对应的数字应更新成在这个单词前面一个字母上的不在字典中的字符的个数。考虑到这种情况在j不断遍历的过程中可能有好几个，选择可以留下个数最少的那个进行更新。\n",
    " \n",
    "#   f. 更新到最后一个位置就是所有在他之前的不在字典中的字母的个数。需要注意的是，dp在更新后总是从1开始的。比如，如果sentence只有一个单词，那么dp在第一个循环后变为1,0。之后，如果单词在字典里dp变为[1,1],如果不在就变为[1,2]。因此dp中所有位子上的数字都多加了1。在最后返回答案的时候减掉。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        #d={}.fromkeys(dictionary)\n",
    "        #d=dictionary\n",
    "        d=set(dictionary)\n",
    "        n=len(sentence)\n",
    "        f=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            f[i]=f[i-1]+1\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in d:\n",
    "                    f[i]=min(f[i],f[j])\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        n=len(sentence)\n",
    "        dp=[i for i in range(n+1)]\n",
    "        s=set(dictionary)\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(0,i):\n",
    "                if sentence[j:i] in s:\n",
    "                    dp[i]=min(dp[i],dp[j])\n",
    "                else:\n",
    "                    dp[i]=min(dp[i],dp[j]+i-j)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        hashtable = collections.defaultdict(list)\n",
    "        for word in dictionary:\n",
    "            \n",
    "            hashtable[word[-1]].append(word)\n",
    "        n = len(sentence)\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            dp[i] = dp[i-1] + 1\n",
    "            if sentence[i-1] in hashtable:\n",
    "                for word in hashtable[sentence[i-1]]:\n",
    "                    l = i - len(word)\n",
    "                    if l >= 0 and word == sentence[l:i]:\n",
    "                        dp[i] = min(dp[i], dp[l])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        #d={}.fromkeys(dictionary)\n",
    "        n=len(sentence)\n",
    "        f=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            f[i]=f[i-1]+1\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in dictionary:\n",
    "                    f[i]=min(f[i],f[j])\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        d={}.fromkeys(dictionary)\n",
    "        n=len(sentence)\n",
    "        dp=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            dp[i]=dp[i-1]+1\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in d:\n",
    "                    dp[i]=min(dp[i],dp[j])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        hashtable = collections.defaultdict(list)\n",
    "        for word in dictionary:\n",
    "            \n",
    "            hashtable[word[-1]].append(word)\n",
    "        n = len(sentence)\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            dp[i] = dp[i-1] + 1\n",
    "            if sentence[i-1] in hashtable:\n",
    "                for word in hashtable[sentence[i-1]]:\n",
    "                    l = i - len(word)\n",
    "                    if l >= 0 and word == sentence[l:i]:\n",
    "                        dp[i] = min(dp[i], dp[l])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        d={}.fromkeys(dictionary)\n",
    "        n=len(sentence)\n",
    "        f=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            f[i]=f[i-1]+1\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in d:\n",
    "                    f[i]=min(f[i],f[j])\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        d = set(dictionary)\n",
    "        n = len(sentence)\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            f[i] = f[i - 1] + 1\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in d:\n",
    "                    f[i] = min(f[i], f[j])\n",
    "        return f[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        d={}.fromkeys(dictionary)\n",
    "        n=len(sentence)\n",
    "        f=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            f[i]=f[i-1]+1\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in d:\n",
    "                    f[i]=min(f[i],f[j])\n",
    "        return f[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        dic = set(dictionary)\n",
    "        n = len(sentence)\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            f[i] = f[i - 1] + 1\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in dic:\n",
    "                    f[i] = min(f[i], f[j])\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        dictionary = set(dictionary)\n",
    "        n = len(sentence)\n",
    "        dp = [n]*(n+1)\n",
    "        dp[0] = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i,-1,-1):\n",
    "                if(sentence[j:i+1] in dictionary):\n",
    "                    dp[i+1] = min(dp[i+1], dp[j])\n",
    "                else:\n",
    "                    dp[i+1] = min(dp[i+1], dp[j]+i-j+1)\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        n = len(sentence)\n",
    "        dp = [0] * (n + 1)\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = i\n",
    "            for word in dictionary:\n",
    "                l = len(word)\n",
    "                if i >= l:\n",
    "                    if sentence[i - l : i] == word:\n",
    "                    # print (f'check\"{sentence[i - l : i]}\"')\n",
    "                        dp[i] = min(dp[i], dp[i - l], dp[i - 1] + 1)\n",
    "                    else:\n",
    "                        dp[i] = min(dp[i], dp[i - l] + l, dp[i - 1] + 1)\n",
    "                else:\n",
    "                    # print(f'n is {n}, and dp[{i}], dp[{i - l}], dp[{i - 1}]')\n",
    "                    dp[i] = min(dp[i], dp[i - 1] + 1)\n",
    "        \n",
    "        # print (dp)\n",
    "        return dp[n]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        d={}.fromkeys(dictionary)\n",
    "        n=len(sentence)\n",
    "        f=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            f[i]=f[i-1]+1\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in d:\n",
    "                    f[i]=min(f[i],f[j])\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        n = len(sentence)\n",
    "        dp = [inf]*(n+1)\n",
    "        dp[0] = 0\n",
    "        dictionary= set(dictionary)\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in dictionary:\n",
    "                    dp[i] = min(dp[i],dp[j])\n",
    "                else:\n",
    "                    dp[i] = min(dp[i],dp[j]+i-j)\n",
    "        # print(dp)\n",
    "        return dp[-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "\n",
    "        # dp[i] 表示达到下标i，之前未识别的字母个数\n",
    "        \n",
    "\n",
    "        dp = [0] * (len(sentence)+1)\n",
    "        \n",
    "\n",
    "        for i in range(1,len(sentence)+1):\n",
    "            dp[i] = dp[i-1]+1\n",
    "            # dp[i]最坏的情况就是当前遍历的这个i为单独的未识别字符，           \n",
    "            for j in range(i+1):\n",
    "                if sentence[j:i] in dictionary:\n",
    "                    dp[i] = min(dp[i],dp[j])\n",
    "                \n",
    "\n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# dictionary = [\"looked\",\"just\",\"like\",\"her\",\"brother\"]\n",
    "# sentence = \"jesslookedjustliketimherbrother\"\n",
    "\n",
    "# a.遍历的顺序：第一层遍历从sentence的第一个字母遍历到最后一个字母。这次遍历代表的是每个可能的单词的最后一个字母所在的位置（i）\n",
    "\n",
    "# 。第二层遍历从最后一个字母所在的位子往前遍历到sentence的第一个字母。这次遍历表示的是可能的单词第一个字母所在的位置（j）。\n",
    "\n",
    "\n",
    "# 通过这两层遍历，i与j中间的所框定的内容就表示的是若以该字母为某个单词的最后一个字母，所有可能的单词的情况。 \n",
    "\n",
    "\n",
    "# b. 特别的，字典中可能存在单个字母所构成的单词的情况。所以j的遍历要到i所对应的元素为止。确保一个字母构成的单词也可能出现。 \n",
    "\n",
    "# c. 构建一个list来储存动态规划中对每个元素而言，其之前的内容中不在字典内的字符的个数。\n",
    "\n",
    "#  d. 如果字典为空，那么dp指针从左往右的过程中,每次向右移动就加上一个新的字符。 \n",
    " \n",
    "#  e. 考虑字典不为空，那么如果出现了字典的内容，那么对应单词的最后一个字母的位置就应该剔除掉之前因为误以为该单词不在字典中而错误累加的个数（误加了单词的长度的个数）。换言之，单词的最后一个字母的位置对应的数字应更新成在这个单词前面一个字母上的不在字典中的字符的个数。考虑到这种情况在j不断遍历的过程中可能有好几个，选择可以留下个数最少的那个进行更新。\n",
    " \n",
    "#   f. 更新到最后一个位置就是所有在他之前的不在字典中的字母的个数。需要注意的是，dp在更新后总是从1开始的。比如，如果sentence只有一个单词，那么dp在第一个循环后变为1,0。之后，如果单词在字典里dp变为[1,1],如果不在就变为[1,2]。因此dp中所有位子上的数字都多加了1。在最后返回答案的时候减掉。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        if not sentence:\n",
    "            return 0\n",
    "        seen = set(dictionary)\n",
    "\n",
    "        dp = [0] * len(sentence)\n",
    "        if sentence[0] in seen:\n",
    "            dp[0] = 0\n",
    "        else:\n",
    "            dp[0] = 1\n",
    "\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            dp[i] = dp[i - 1] + 1\n",
    "            for j in range(i + 1):\n",
    "                ss = sentence[j:i + 1]\n",
    "                if ss in seen:\n",
    "                    dp[i] = min(dp[i], dp[j - 1] if j - 1 >= 0 else 0)\n",
    "        \n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        if len(sentence) == 0:\n",
    "            return 0\n",
    "        dict_better = {}\n",
    "        for w in dictionary:\n",
    "            dict_better[w] = ''\n",
    "        best_till_n = [inf for _ in sentence]\n",
    "        for end in range(1, len(sentence)+1):\n",
    "            for start in range(0, end):\n",
    "                left = 0 if start == 0 else best_till_n[start-1]\n",
    "                right = 0 if sentence[start:end] in dict_better else (end-start)\n",
    "                if best_till_n[end-1] > left + right:\n",
    "                    best_till_n[end-1] = left + right\n",
    "        return best_till_n[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        # 暴力\n",
    "        dictionary = {*dictionary}\n",
    "        n = len(sentence)\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            dp[i] = dp[i-1] + 1\n",
    "            for j in range(i+1):\n",
    "                if sentence[j:i] in dictionary:\n",
    "                    dp[i] = min(dp[i],dp[j])\n",
    "        return dp[n] - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        cols = len(sentence) + 1\n",
    "        dp = [float('inf')] * cols \n",
    "        dp[0] = 0 \n",
    "\n",
    "        for i in range(1, cols):\n",
    "            # dp[i] = dp[i-1] + 1\n",
    "            for j in range(i):                \n",
    "                if sentence[j: i] in dictionary:\n",
    "                    dp[i] = min(dp[i], dp[j])\n",
    "                else:\n",
    "                    dp[i] = min(dp[i], dp[j] + i-j)\n",
    "                    \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        dictionary = set(dictionary)\n",
    "        n = len(sentence)\n",
    "        dp = [n]*(n+1)\n",
    "        dp[0] = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i,-1,-1):\n",
    "                if(sentence[j:i+1] in dictionary):\n",
    "                    dp[i+1] = min(dp[i+1], dp[j])\n",
    "                else:\n",
    "                    dp[i+1] = min(dp[i+1], dp[j]+i-j+1)\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        #d={}.fromkeys(dictionary)\n",
    "        d=dictionary\n",
    "        n=len(sentence)\n",
    "        f=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            f[i]=f[i-1]+1\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in d:\n",
    "                    f[i]=min(f[i],f[j])\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        st = set(dictionary)\n",
    "        n = len(sentence)\n",
    "        f = [0x3f3f3f3f] * (n + 1)\n",
    "        f[0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                s = \"\".join(sentence[j - 1:i])\n",
    "                if s in st: f[i] = min(f[j - 1], f[i])\n",
    "                else: f[i] = min(f[i], f[j - 1] + i - j + 1)\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        n = len(sentence)\n",
    "        dp = [inf]*(n+1)\n",
    "        dp[0] = 0\n",
    "        dictionary= set(dictionary)\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in dictionary:\n",
    "                    dp[i] = min(dp[i],dp[j])\n",
    "                else:\n",
    "                    dp[i] = min(dp[i],dp[j]+i-j)\n",
    "        print(dp)\n",
    "        return dp[-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        d={}.fromkeys(dictionary)\n",
    "\n",
    "        n=len(sentence)\n",
    "        dp=[0]*(n+1)\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            dp[i]=dp[i-1]+1\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in dictionary:\n",
    "                    dp[i]=min(dp[j],dp[i])\n",
    "\n",
    "\n",
    "        return dp[-1]   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        dic = set(dictionary)\n",
    "        n = len(sentence)\n",
    "\n",
    "        dp = [float('inf')]*(n+1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(0, i):\n",
    "                if sentence[j:i] in dic:\n",
    "                    dp[i] = min(dp[i], dp[j])\n",
    "                else:\n",
    "                    dp[i] = min(dp[i], i-j+dp[j])\n",
    "            pass\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], s: str) -> int:\n",
    "        dictionary = set([w for w in dictionary if s.find(w) != -1])\n",
    "        dp = [0] + [len(s)] * len(s)\n",
    "        for i in range(1, len(s) + 1): \n",
    "            for j in range(1, i+1):\n",
    "                if s[j-1:i] in dictionary:\n",
    "                    dp[i] = min(dp[i], dp[j-1])\n",
    "                else:\n",
    "                    dp[i] = min(dp[i], dp[j-1] + i - j + 1)\n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        d={}.fromkeys(dictionary)\n",
    "        n=len(sentence)\n",
    "        f=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            f[i]=f[i-1]+1\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in d:\n",
    "                    f[i]=min(f[i],f[j])\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        n = len(sentence)\n",
    "        dp = [0] * (n + 1)  # dp[i]表示前i个字符中未识别的字符数\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i - 1] + 1  # 先假设当前字符是未识别的字符\n",
    "            for word in dictionary:\n",
    "                if i >= len(word) and sentence[i - len(word):i] == word:\n",
    "                    dp[i] = min(dp[i], dp[i - len(word)])\n",
    "\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        dic = set(dictionary)\n",
    "        n = len(sentence)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        f = [i + 1 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            temp = \"\"\n",
    "            for j in range(i, -1, -1):\n",
    "                temp = sentence[j] + temp\n",
    "                temp_score = f[j - 1] if j - 1 >= 0 else 0\n",
    "                if temp in dic:\n",
    "                    f[i] = min(f[i], temp_score)\n",
    "                else:\n",
    "                    f[i] = min(f[i], temp_score + len(temp))\n",
    "        return f[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "\t\tans = [i for i in range(len(sentence) + 1)]\n",
    "\t\tfor i in range(len(sentence)):\n",
    "\t\t\tfor word in dictionary:\n",
    "\t\t\t\tif sentence[i:].startswith(word):\n",
    "\t\t\t\t\tans[i + len(word)] = min(ans[i], ans[i + len(word)])\n",
    "\t\t\tans[i + 1] = min(ans[i] + 1, ans[i + 1])\n",
    "\t\treturn ans[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        \"\"\"\n",
    "        动态规划\n",
    "        状态定义：f[i]，0 <= i <= len(sentence)\n",
    "            集合：前 i 个字符所有可能的划分方式\n",
    "            属性：Min(未识别的字符数)\n",
    "        状态转移：\n",
    "            集合划分：\n",
    "                第 i 个字符无法与前面任何一个子串组成单词：f[i - 1] + 1\n",
    "                第 i 个字符可以与前面某个子串组成单词：f[j]\n",
    "                if sentence[j:i] in dictionary，0 <= j <= i - 1\n",
    "            初始化：f[0] = 0，当 sentence 为空字符串时，未识别字符数为 0\n",
    "            答案：f[-1]\n",
    "        \"\"\"\n",
    "        d = {}.fromkeys(dictionary)\n",
    "        n = len(sentence)\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            f[i] = f[i - 1] + 1\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in d:\n",
    "                    f[i] = min(f[i], f[j])\n",
    "        return f[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        # 暴力\n",
    "        dictionary = {*dictionary}\n",
    "        n = len(sentence)\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        for i in range(1,n+1):\n",
    "            dp[i] = dp[i-1] + 1\n",
    "            for j in range(i,-1,-1):\n",
    "                if sentence[j:i] in dictionary:\n",
    "                    dp[i] = min(dp[i],dp[j])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        cols = len(sentence) + 1 \n",
    "        dp = [len(sentence)] * cols \n",
    "        dp[0] = 0 \n",
    "        dic = dict.fromkeys(dictionary, 0)\n",
    "        for i in range(1, cols):\n",
    "            for j in range(i):\n",
    "                if sentence[j: i] in dic:\n",
    "                    dp[i] = min(dp[i], dp[j])\n",
    "                else:\n",
    "                    dp[i] = min(dp[i], dp[j] + i-j)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        cols = len(sentence) + 1\n",
    "        dp = [float('inf')] * cols \n",
    "        dp[0] = 0 \n",
    "\n",
    "        for i in range(1, cols):\n",
    "            # dp[i] = dp[i-1] + 1\n",
    "            for j in range(i):                \n",
    "                if sentence[j: i] in dictionary:\n",
    "                    dp[i] = min(dp[i], dp[j])\n",
    "                else:\n",
    "                    dp[i] = min(dp[i], dp[j] + i-j)\n",
    "                    \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        if len(sentence) <= 0: return 0\n",
    "        if len(dictionary) <= 0: return len(sentence)\n",
    "        dictionary = set(dictionary)\n",
    "        dp = [0] * (len(sentence) + 1)  # 最后一个0是哨兵\n",
    "        for i in range(len(sentence)):\n",
    "            dp[i] = dp[i - 1] + 1\n",
    "            # 遍历所有单词，看能否和「以i为结尾的子串」一样\n",
    "            for dic in dictionary:\n",
    "                if (len(dic) <= i + 1) and sentence[i + 1 - len(dic):i + 1] == dic:\n",
    "                    dp[i] = min(dp[i], dp[i - len(dic)])\n",
    "        return dp[-2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        if len(sentence) <= 0: return 0\n",
    "        if len(dictionary) <= 0: return len(sentence)\n",
    "\n",
    "        dp = [0] * (len(sentence) + 1)  # 最后一个0是哨兵\n",
    "        for i in range(len(sentence)):\n",
    "            dp[i] = dp[i - 1] + 1\n",
    "            # 遍历所有单词，看能否和「以i为结尾的子串」一样\n",
    "            for dic in dictionary:\n",
    "                if (len(dic) <= i + 1) and sentence[i + 1 - len(dic):i + 1] == dic:\n",
    "                    dp[i] = min(dp[i], dp[i - len(dic)])\n",
    "        return dp[-2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        d={}.fromkeys(dictionary)\n",
    "\n",
    "        n=len(sentence)\n",
    "        dp=[0]*(n+1)\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            dp[i]=dp[i-1]+1\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in d:\n",
    "                    dp[i]=min(dp[j],dp[i])\n",
    "\n",
    "        return dp[-1]   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        dic_set = set(dictionary)\n",
    "        n = len(sentence)\n",
    "        dp = [0] * (n + 1)\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i - 1] + 1  # 假设第 i 个字符未识别\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in dic_set:\n",
    "                    dp[i] = min(dp[i], dp[j])\n",
    "                    \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        dset = set(dictionary)\n",
    "        n = len(sentence)\n",
    "        dp = [0] * (n + 1) # dp[i]: 前 i 个字符所有可能的划分方式中，最少的未识别字符数\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i - 1] + 1 # case 1: 当第 i 个字符无法与前面任何一个子串组成单词时，则第 i 个字符将算作一个未识别字符\n",
    "            for j in range(i): # case 2: 从头遍历，检查第 i 个字符是否可以与前面某个子串组成单词\n",
    "                if sentence[j:i] in dset:  # 子串存在于字典中\n",
    "                    dp[i] = min(dp[i], dp[j])\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        n = len(sentence)\n",
    "        dp = [inf]*(n+1)\n",
    "        dp[0] = 0\n",
    "        dictionary= set(dictionary)\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in dictionary:\n",
    "                    dp[i] = min(dp[i],dp[j])\n",
    "                else:\n",
    "                    dp[i] = min(dp[i],dp[j]+i-j)\n",
    "        print(dp)\n",
    "        return dp[-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        n = len(sentence)\n",
    "        dp = [inf]*(n+1)\n",
    "        dp[0] = 0\n",
    "        dictionary= set(dictionary)\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in dictionary:\n",
    "                    dp[i] = min(dp[i],dp[j])\n",
    "                else:\n",
    "                    dp[i] = min(dp[i],dp[j]+i-j)\n",
    "        # print(dp)\n",
    "        return dp[-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        cols = len(sentence) + 1 \n",
    "        dp = [len(sentence)] * cols \n",
    "        dp[0] = 0 \n",
    "\n",
    "        for i in range(1, cols):\n",
    "            for j in range(i):\n",
    "                if sentence[j: i] in dictionary:\n",
    "                    dp[i] = min(dp[i], dp[j]+0)\n",
    "                else:\n",
    "                    dp[i] = min(dp[i], dp[j] + i-j)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        cols = len(sentence) + 1 \n",
    "        dp = [len(sentence)] * cols \n",
    "        dp[0] = 0 \n",
    "        dic = dict.fromkeys(dictionary)\n",
    "        for i in range(1, cols):\n",
    "            for j in range(i):\n",
    "                if sentence[j: i] in dic:\n",
    "                    dp[i] = min(dp[i], dp[j]+0)\n",
    "                else:\n",
    "                    dp[i] = min(dp[i], dp[j] + i-j)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        cols = len(sentence) + 1 \n",
    "        dp = [len(sentence)] * cols \n",
    "        dp[0] = 0 \n",
    "        dic = dict.fromkeys(dictionary)\n",
    "        for i in range(1, cols):\n",
    "            for j in range(i):\n",
    "                if sentence[j: i] in dic:\n",
    "                    dp[i] = min(dp[i], dp[j]+0)\n",
    "                else:\n",
    "                    dp[i] = min(dp[i], dp[j] + i-j)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        cols = len(sentence) + 1 \n",
    "        dp = [len(sentence)] * cols \n",
    "        dp[0] = 0 \n",
    "        dic = dict.fromkeys(dictionary, 0)\n",
    "        for i in range(1, cols):\n",
    "            for j in range(i):\n",
    "                if sentence[j: i] in dic:\n",
    "                    dp[i] = min(dp[i], dp[j])\n",
    "                else:\n",
    "                    dp[i] = min(dp[i], dp[j] + i-j)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        dic_set = set(dictionary)\n",
    "        n = len(sentence)\n",
    "        dp = [0] * (n + 1)\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i - 1] + 1  # 假设第 i 个字符未识别\n",
    "            for j in range(i):\n",
    "                if sentence[j:i] in dic_set:\n",
    "                    dp[i] = min(dp[i], dp[j])\n",
    "                    \n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        # 动态规划 + 递归\n",
    "        dictionary = {w for w in dictionary if sentence.find(w) != -1}\n",
    "        lens = list({len(w) for w in dictionary})  # 统计单词长度\n",
    "        lens.sort(reverse = True)  # 长度排序\n",
    "        n, i = len(sentence), 0  # 总长，校验位置\n",
    "        @functools.lru_cache(maxsize=1000)\n",
    "        def sol(i) :\n",
    "            if i >= n : return 0\n",
    "            tails = [sol(i+l) for l in lens if i+l <= n and sentence[i:i+l] in dictionary] # 尝试所有可能单词\n",
    "            tails += [1+sol(i+1)] # 跳过当前字符\n",
    "            return (min(tails) if tails else 0)\n",
    "        return sol(0)\n",
    "\n",
    "        \"\"\"\n",
    "        动态规划\n",
    "        状态定义：dp[i]，0 <= i <= len(sentence)\n",
    "            集合：前 i 个字符所有可能的划分方式\n",
    "            属性：Min(未识别的字符数)\n",
    "        状态转移：\n",
    "            集合划分：\n",
    "                第 i 个字符无法与前面任何一个子串组成单词：dp[i - 1] + 1\n",
    "                第 i 个字符可以与前面某个子串组成单词：dp[j]\n",
    "                if sentence[j:i] in dictionary，0 <= j <= i - 1\n",
    "            初始化：dp[0] = 0，当 sentence 为空字符串时，未识别字符数为 0\n",
    "            答案：dp[-1]\n",
    "        \"\"\"\n",
    "        # 动态规划\n",
    "        d = set([x for x in dictionary if x in sentence])  # 筛选存在sentence中的单词并哈希化\n",
    "        n = len(sentence)\n",
    "        dp = [n for _ in range(n+1)]  # 动态规划数组初始化\n",
    "        dp[0] = 0  # 初始变量0\n",
    "        for i in range(n+1):\n",
    "            # 找得到的就保留未识别字符的最小值（即比上一个加一要少），找不到就+1后移\n",
    "            dp[i] = min(dp[i], dp[i-1]+1)  # 当前dp[i]赋值\n",
    "            for x in d:  # 遍历字典单词 \n",
    "                j = i + len(x)\n",
    "                if sentence[i:j] == x:\n",
    "                    dp[j] = min(dp[i], dp[j])  # 对dp[j] 赋值\n",
    "        return dp[-1]  # 输出最后一个的未识别字符\n",
    "\n",
    "\n",
    "        # 动态规划\n",
    "        dictionary = set(dictionary)\n",
    "        n = len(sentence)\n",
    "        dp = [0] + [n for _ in range(n)]  # 动态规划变量 - 最少未识别字符数\n",
    "        for j in range(1, n+1):  # 1~n\n",
    "            for i in range(j):  # 0~j\n",
    "                if sentence[i:j] in dictionary:\n",
    "                    dp[j] = min(dp[j], dp[i])  # \n",
    "                else:\n",
    "                    dp[j] = min(dp[j], dp[i]+j-i)  # 状态转移方程\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def f(self, p):\n",
    "        if p == len(self.s) or self.s[p:] in self.l: return 0\n",
    "        res = []\n",
    "        for x in self.l:\n",
    "            if self.s[p:].startswith(x): res.append(self.f(p+len(x)))\n",
    "        return min(res + [1+self.f(p+1)])\n",
    "\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        self.l, self.s = dictionary, sentence\n",
    "        return self.f(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        dictionary = set(dictionary)\n",
    "\n",
    "        # 统计单词长度\n",
    "        lens = list({len(w) for w in dictionary})\n",
    "        lens.sort(reverse = True)\n",
    "\n",
    "        N, res, i = len(sentence), 0, 0\n",
    "        @functools.lru_cache(maxsize=1000)\n",
    "        def sol(i) :\n",
    "            if i >= N : return 0\n",
    "            tails = [sol(i+l) for l in lens if i+l <= N and sentence[i:i+l] in dictionary] # 尝试所有可能单词\n",
    "            tails += [1+sol(i+1)] # 跳过当前字符\n",
    "            return (min(tails) if tails else 0)\n",
    "\n",
    "        return sol(0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def f(self, p):\n",
    "        if p == len(self.s) or self.s[p:] in self.l: return 0\n",
    "        res = 1+self.f(p+1)\n",
    "        for x in self.l: res = min(res, self.f(p+len(x))) if self.s[p:].startswith(x) else res\n",
    "        return res\n",
    "\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        self.l, self.s = dictionary, sentence\n",
    "        return self.f(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        dct = defaultdict(list)\n",
    "        for d in dictionary:\n",
    "            dct[d[0]].append(d)\n",
    "        dc = {}\n",
    "        def dfs(s):\n",
    "            if not s:\n",
    "                return 0\n",
    "            tmp = len(s)\n",
    "            if dc.get(s) is not None:\n",
    "                return dc[s]\n",
    "            for nxt in dct[s[0]]:\n",
    "                if s.startswith(nxt):\n",
    "                    tmp = min(tmp, dfs(s[len(nxt):]))\n",
    "            tmp = min(tmp, 1 + dfs(s[1:]))\n",
    "            dc[s] = tmp\n",
    "            return tmp\n",
    "        res = dfs(sentence)\n",
    "        # print(dct)\n",
    "        # print(dc)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        n = len(sentence)\n",
    "        @cache\n",
    "        def dfs(words):\n",
    "            if not words:\n",
    "                return 0\n",
    "            res,flag = inf,True\n",
    "            for word in dictionary:\n",
    "                re = 0\n",
    "                if word in words:\n",
    "                    flag = False\n",
    "                    for c in words.split(word):\n",
    "                        re += dfs(c)\n",
    "                    res = min(res,re)\n",
    "            if flag:return len(words)\n",
    "            return res\n",
    "        return dfs(sentence)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        dict_tree = {}\n",
    "        for word in dictionary:\n",
    "            record = dict_tree\n",
    "            for c in word[::-1]:\n",
    "                if c not in record:\n",
    "                    record[c] = {}\n",
    "                record = record[c]\n",
    "            record['end'] = True\n",
    "        \n",
    "        n = len(sentence)\n",
    "        dp = [float('inf') for _ in range(n+1)]\n",
    "        dp[0] = 0\n",
    "        for i in range(1, n+1):\n",
    "            record = dict_tree\n",
    "            dp[i] = dp[i-1]+1\n",
    "            for j in range(i, 0, -1):\n",
    "                if sentence[j-1] not in record:\n",
    "                    break\n",
    "                elif 'end' in record[sentence[j-1]]:\n",
    "                    dp[i] = min(dp[i], dp[j-1])\n",
    "                record = record[sentence[j-1]]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = {}\n",
    "    def insert(self, word):\n",
    "        cur=self.root\n",
    "        for c in word:\n",
    "            if c not in cur:\n",
    "                cur[c]={}\n",
    "            cur=cur[c]\n",
    "        cur['#']={}\n",
    "    def search_respace(self, word):\n",
    "        cur=self.root\n",
    "        for c in word:\n",
    "            if c not in cur:\n",
    "                return False\n",
    "            cur=cur[c]\n",
    "        if '#' in cur: \n",
    "            return 1\n",
    "        else: \n",
    "            return 2\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], s: str) -> int:\n",
    "        # 构建前缀树\n",
    "        word_tree=Trie()\n",
    "        for w in dictionary:\n",
    "            word_tree.insert(w[::-1])\n",
    "        # 动态规划迭代\n",
    "        # dp[i]是s[0,...,i-1]的最少未识别字符数 (dp[0]=0)\n",
    "        dp=[len(s) for _ in range(len(s)+1)]\n",
    "        dp[0]=0\n",
    "        for j in range(1, len(s)+1):\n",
    "            # 从后往前 如果s[i:j]=s[i..j-1]不是前缀 则没必要再往前查找\n",
    "            for i in range(j-1,-1,-1):\n",
    "                word=s[i:j][::-1] #别忘记逆向\n",
    "                search_res=word_tree.search_respace(word)\n",
    "                if search_res==False:\n",
    "                    dp[j]=min(dp[j], dp[i]+j-i)\n",
    "                    break\n",
    "                elif search_res==1:\n",
    "                    dp[j]=min(dp[j], dp[i])\n",
    "                else:\n",
    "                    dp[j]=min(dp[j], dp[i]+j-i)   \n",
    "        return dp[len(s)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = [{}, False]\n",
    "    \n",
    "    def add(self, word):\n",
    "        curr = self.root\n",
    "        for c in word[::-1]: # 倒着组装字典树，因为后面dp的时候是倒着检查单词的\n",
    "            if c not in curr[0]:\n",
    "                curr[0][c] = [{}, False]\n",
    "            curr = curr[0][c]\n",
    "        curr[0][\"word\"] = word\n",
    "        curr[1] = True\n",
    "    \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        n = len(sentence)\n",
    "\n",
    "        # 构造字典树\n",
    "        trie = Trie()   \n",
    "        for word in dictionary:\n",
    "            trie.add(word)\n",
    "\n",
    "        # dp[i] 表示前i个字符，最少的未被识别的字符数量\n",
    "        dp = [float(\"inf\") for _ in range(n+1)]\n",
    "\n",
    "        dp[0] = 0 # 没有字符，所以未被识别的字符数量也是0\n",
    "\n",
    "        for i in range(1, n+1): # 前i个字符\n",
    "\n",
    "            # 情况A. 当前字符(i-i位置)，不作为字典中单词的一个字符，而是作为一个不可识别字符\n",
    "            dp[i] = dp[i-1] + 1\n",
    "\n",
    "            # 情况B. 当前字符(i-i位置)，作为一个字典中的单词的一个字符，\n",
    "            # 则需要从当前位置i-1开始，遍历sentence中的字符i-1~0，查询各个以i-i位置结尾的单词，找到dp最小值\n",
    "            curr = trie.root\n",
    "            for j in range(i-1, -1, -1): # j从i-1位置开始往前退，找到一个单词，就算一次dp\n",
    "                c = sentence[j]\n",
    "                if c not in curr[0]:\n",
    "                    break # 非单词，退出去，dp不更新，只能用情况A的值（当前位置属于不可识别）\n",
    "                else:\n",
    "                    # j~i-1 这一区间的字符，属于一个完整单词\n",
    "                    # 则当前dp值等于j-1位置上的dp值：dp[j-1+1]\n",
    "                    if curr[0][c][1]:\n",
    "                        dp[i] = min(dp[i], dp[j]) # 取情况A和情况B的最小值（同时情况B有多种组合，这里也是在取最小值）\n",
    "                    \n",
    "                    curr = curr[0][c] # 继续深入字典树，找下一个符合条件的单词，判断dp值\n",
    "\n",
    "        return dp[n]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = [{}, False]\n",
    "    \n",
    "    def add(self, word):\n",
    "        curr = self.root\n",
    "        for c in word[::-1]: # 重要！！！ 倒着组装字典树，因为后面dp的时候是倒着检查单词的\n",
    "            if c not in curr[0]:\n",
    "                curr[0][c] = [{}, False]\n",
    "            curr = curr[0][c]\n",
    "        curr[0][\"word\"] = word\n",
    "        curr[1] = True\n",
    "    \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        n = len(sentence)\n",
    "\n",
    "        # 构造字典树\n",
    "        trie = Trie()   \n",
    "        for word in dictionary:\n",
    "            trie.add(word)\n",
    "\n",
    "        # dp[i] 表示前i个字符，最少的未被识别的字符数量\n",
    "        dp = [float(\"inf\") for _ in range(n+1)]\n",
    "\n",
    "        dp[0] = 0 # 没有字符，所以未被识别的字符数量也是0\n",
    "\n",
    "        for i in range(1, n+1): # 前i个字符\n",
    "\n",
    "            # 情况A. 当前字符(i-i位置)，不作为字典中单词的一个字符，而是作为一个不可识别字符\n",
    "            dp[i] = dp[i-1] + 1\n",
    "\n",
    "            # 情况B. 当前字符(i-i位置)，作为一个字典中的单词的一个字符，\n",
    "            # 则需要从当前位置i-1开始，遍历sentence中的字符i-1~0，查询各个以i-i位置结尾的单词，找到dp最小值\n",
    "            curr = trie.root\n",
    "            for j in range(i-1, -1, -1): # j从i-1位置开始往前退，找到一个单词，就算一次dp （因为前面字典树是倒着组装的，所以这里可以倒着找单词！）\n",
    "                c = sentence[j]\n",
    "                if c not in curr[0]:\n",
    "                    break # 非单词，退出去，dp不更新，只能用情况A的值（当前位置属于不可识别）\n",
    "                else:\n",
    "                    # j~i-1 这一区间的字符，属于一个完整单词\n",
    "                    # 则当前dp值等于j-1位置上的dp值：dp[j-1+1]\n",
    "                    if curr[0][c][1]:\n",
    "                        dp[i] = min(dp[i], dp[j]) # 取情况A和情况B的最小值（同时情况B有多种组合，这里也是在取最小值）\n",
    "                    \n",
    "                    curr = curr[0][c] # 继续深入字典树，找下一个符合条件的单词，判断dp值\n",
    "\n",
    "        return dp[n]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = [{}, False]\n",
    "    \n",
    "    def add(self, word):\n",
    "        curr = self.root\n",
    "        for c in word[::-1]: # 倒着组装字典树，因为后面dp的时候是倒着检查单词的\n",
    "            if c not in curr[0]:\n",
    "                curr[0][c] = [{}, False]\n",
    "            curr = curr[0][c]\n",
    "        curr[0][\"word\"] = word\n",
    "        curr[1] = True\n",
    "    \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        n = len(sentence)\n",
    "\n",
    "        # 构造字典树\n",
    "        trie = Trie()   \n",
    "        for word in dictionary:\n",
    "            trie.add(word)\n",
    "\n",
    "        # dp[i] 表示前i个字符，最少的未被识别的字符数量\n",
    "        dp = [float(\"inf\") for _ in range(n+1)]\n",
    "\n",
    "        dp[0] = 0 # 没有字符，所以未被识别的字符数量也是0\n",
    "\n",
    "        for i in range(1, n+1): # 前i个字符\n",
    "\n",
    "            # 情况A. 当前字符(i-i位置)，不作为字典中单词的一个字符，而是作为一个不可识别字符\n",
    "            dp[i] = dp[i-1] + 1\n",
    "\n",
    "            # 情况B. 当前字符，作为一个字典中的单词的一个字符，则需要遍历0~i-1，遍历不同的字典内单词，找到dp最小值\n",
    "            curr = trie.root\n",
    "            for j in range(i-1, -1, -1):\n",
    "                c = sentence[j]\n",
    "                if c not in curr[0]:\n",
    "                    break\n",
    "                else:\n",
    "\n",
    "                    if curr[0][c][1]:\n",
    "                        # 位置j的字符，属于单词的尾巴，则j-1位置上的dp为：dp[j-1+1]\n",
    "                        dp[i] = min(dp[i], dp[j])\n",
    "                    \n",
    "                    curr = curr[0][c]\n",
    "\n",
    "        return dp[n]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = [{}, False]\n",
    "    \n",
    "    def add(self, word):\n",
    "        curr = self.root\n",
    "        for c in word[::-1]: # 重要！！！ 倒着组装字典树，因为后面dp的时候是倒着检查单词的\n",
    "            if c not in curr[0]:\n",
    "                curr[0][c] = [{}, False]\n",
    "            curr = curr[0][c]\n",
    "        # curr[0][\"word\"] = word\n",
    "        curr[1] = True\n",
    "    \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        n = len(sentence)\n",
    "\n",
    "        # 构造字典树\n",
    "        trie = Trie()   \n",
    "        for word in dictionary:\n",
    "            trie.add(word)\n",
    "\n",
    "        # dp[i] 表示前i个字符，最少的未被识别的字符数量\n",
    "        dp = [float(\"inf\") for _ in range(n+1)]\n",
    "\n",
    "        dp[0] = 0 # 没有字符，所以未被识别的字符数量也是0\n",
    "\n",
    "        for i in range(1, n+1): # 前i个字符\n",
    "\n",
    "            # 情况A. 当前字符(i-i位置)，不作为字典中单词的一个字符，而是作为一个不可识别字符\n",
    "            dp[i] = dp[i-1] + 1\n",
    "\n",
    "            # 情况B. 当前字符(i-i位置)，作为一个字典中的单词的一个字符，\n",
    "            # 则需要从当前位置i-1开始，遍历sentence中的字符i-1~0，查询各个以i-i位置结尾的单词，找到dp最小值\n",
    "            curr = trie.root\n",
    "            for j in range(i-1, -1, -1): # j从i-1位置开始往前退，找到一个单词，就算一次dp （因为前面字典树是倒着组装的，所以这里可以倒着找单词！）\n",
    "                c = sentence[j]\n",
    "                if c not in curr[0]:\n",
    "                    break # 非单词，退出去，dp不更新，只能用情况A的值（当前位置属于不可识别）\n",
    "                else:\n",
    "                    # j~i-1 这一区间的字符，属于一个完整单词\n",
    "                    # 则当前dp值等于j-1位置上的dp值：dp[j-1+1]\n",
    "                    if curr[0][c][1]:\n",
    "                        dp[i] = min(dp[i], dp[j]) # 取情况A和情况B的最小值（同时情况B有多种组合，这里也是在取最小值）\n",
    "                    \n",
    "                    curr = curr[0][c] # 继续深入字典树，找下一个符合条件的单词，判断dp值\n",
    "\n",
    "        return dp[n]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\r\n",
    "    def __init__(self, dic: List[str] = None) -> None:\r\n",
    "        self.child = {}\r\n",
    "        self.hasvalue = False\r\n",
    "        if dic:\r\n",
    "            for word in dic:\r\n",
    "                self.add(word)\r\n",
    "\r\n",
    "    def add(self, word: str):\r\n",
    "        node = self\r\n",
    "        for char in reversed(word):\r\n",
    "            if char not in node.child:\r\n",
    "                node.child[char] = Trie()\r\n",
    "            node = node.child[char]\r\n",
    "        node.hasvalue = True\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\r\n",
    "        root = Trie(dictionary)\r\n",
    "        n = len(sentence)\r\n",
    "        dp = [0] * (n + 1)  # dp[0] = 0\r\n",
    "\r\n",
    "        for k in range(1, n + 1):\r\n",
    "            # 不尝试识别\r\n",
    "            minUnknown = dp[k - 1] + 1\r\n",
    "            # 尝试识别\r\n",
    "            node = root\r\n",
    "            i = k\r\n",
    "            while i > 0:\r\n",
    "                if sentence[i-1] in node.child:\r\n",
    "                    node = node.child[sentence[i-1]]\r\n",
    "                else:\r\n",
    "                    break\r\n",
    "                if node.hasvalue:\r\n",
    "                    minUnknown = min(minUnknown, dp[i - 1])\r\n",
    "                i -= 1\r\n",
    "            # 分类讨论完毕\r\n",
    "            dp[k] = minUnknown\r\n",
    "\r\n",
    "        return dp[n]\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.is_word = False\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        node = self.root\n",
    "        for ch in word:\n",
    "            if ch not in node.children:\n",
    "                node.children[ch] = TrieNode()\n",
    "            node = node.children[ch]\n",
    "        node.is_word = True\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], s: str) -> int:\n",
    "        # 构建前缀树\n",
    "        word_tree = Trie()\n",
    "        for w in dictionary:\n",
    "            word_tree.insert(w)\n",
    "        n = len(s)\n",
    "        dp=[n-i for i in range(n+1)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            node = word_tree.root\n",
    "            for j in range(i, n):\n",
    "                ch = s[j]\n",
    "                if ch not in node.children:\n",
    "                    dp[i] = min(dp[i], dp[j+1] + j-i+1)\n",
    "                    break\n",
    "                node = node.children[ch]\n",
    "                if node.is_word:\n",
    "                    dp[i] = min(dp[i], dp[j+1])\n",
    "                else:\n",
    "                    dp[i] = min(dp[i], dp[i+1] + j-i+1)\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, dic: List[str] = None) -> None:\n",
    "        self.child = {}\n",
    "        self.hasvalue = False\n",
    "        if dic:\n",
    "            for word in dic:\n",
    "                self.add(word)\n",
    "\n",
    "    def add(self, word: str):\n",
    "        node = self\n",
    "        for char in reversed(word):\n",
    "            if char not in node.child:\n",
    "                node.child[char] = Trie()\n",
    "            node = node.child[char]\n",
    "        node.hasvalue = True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        root = Trie(dictionary)\n",
    "        n = len(sentence)\n",
    "        dp = [0] * (n + 1)  # dp[0] = 0\n",
    "\n",
    "        for k in range(1, n + 1):\n",
    "            # 不尝试识别\n",
    "            minUnknown = dp[k - 1] + 1\n",
    "            # 尝试识别\n",
    "            node = root\n",
    "            i = k\n",
    "            while i > 0:\n",
    "                if sentence[i-1] in node.child:\n",
    "                    node = node.child[sentence[i-1]]\n",
    "                else:\n",
    "                    break\n",
    "                if node.hasvalue:\n",
    "                    minUnknown = min(minUnknown, dp[i - 1])\n",
    "                i -= 1\n",
    "            # 分类讨论完毕\n",
    "            dp[k] = minUnknown\n",
    "\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "\n",
    "        self.child = {}\n",
    "        self.word = \"\"\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word):\n",
    "        cur = self\n",
    "        n = len(word)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            c = word[i]\n",
    "            if c not in cur.child:\n",
    "                cur.child[c] = Trie()\n",
    "            cur = cur.child[c]\n",
    "        cur.child[\"#\"] = {}\n",
    "        cur.word = word\n",
    "        cur.isEnd = True\n",
    "\n",
    "    def find(self, word):\n",
    "        cur = self\n",
    "        for c in word:\n",
    "            if c not in cur.child:\n",
    "                return False\n",
    "            cur = cur.child\n",
    "        return cur.isEnd\n",
    "    \n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        root = Trie()\n",
    "        for word in dictionary:\n",
    "            root.insert(word)\n",
    "        n = len(sentence)\n",
    "        dp = [ float(\"inf\") ] * (n + 1)\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[ i - 1 ] + 1\n",
    "\n",
    "            cur = root\n",
    "            j = i\n",
    "            while j >= 1:\n",
    "                t = sentence[j - 1]\n",
    "                if t not in cur.child:\n",
    "                    break\n",
    "                elif cur.child[t].isEnd:\n",
    "                    dp[i] = min(dp[i], dp[j - 1])\n",
    "                if dp[i] == 0:\n",
    "                    break\n",
    "                cur = cur.child[t]\n",
    "                j -= 1\n",
    "        return dp[n]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "\n",
    "        self.child = {}\n",
    "        self.word = \"\"\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word):\n",
    "        cur = self\n",
    "        n = len(word)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            c = word[i]\n",
    "            if c not in cur.child:\n",
    "                cur.child[c] = Trie()\n",
    "            cur = cur.child[c]\n",
    "        cur.child[\"#\"] = {}\n",
    "        cur.word = word\n",
    "        cur.isEnd = True\n",
    "\n",
    "    def find(self, word):\n",
    "        cur = self\n",
    "        for c in word:\n",
    "            if c not in cur.child:\n",
    "                return False\n",
    "            cur = cur.child\n",
    "        return cur.isEnd\n",
    "    \n",
    "class Solution:\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\n",
    "        root = Trie()\n",
    "        for word in dictionary:\n",
    "            root.insert(word)\n",
    "        n = len(sentence)\n",
    "        dp = [ float(\"inf\") ] * (n + 1)\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[ i - 1 ] + 1\n",
    "\n",
    "            cur = root\n",
    "            j = i\n",
    "            while j >= 1:\n",
    "                t = sentence[j - 1]\n",
    "                if t not in cur.child:\n",
    "                    break\n",
    "                elif cur.child[t].isEnd:\n",
    "                    dp[i] = min(dp[i], dp[j - 1])\n",
    "                if dp[i] == 0:\n",
    "                    break\n",
    "                cur = cur.child[t]\n",
    "                j -= 1\n",
    "        return dp[n]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode(object):\n",
    "\tdef __init__(self):\n",
    "\t\tself.next = {}\n",
    "\t\tself.end = False\n",
    "\n",
    "class Solution:\n",
    "\tdef respace(self, dictionary, sentence):\n",
    "\t\troot = TrieNode()\n",
    "\t\tfor w in dictionary:\n",
    "\t\t\tself.build(root, w, 0)\n",
    "\t\tn = len(sentence)\n",
    "\t\tdp = list(range(n + 1))\n",
    "\t\tfor i in range(n):\n",
    "\t\t\tdp[i + 1] = min(dp[i + 1], dp[i] + 1)\n",
    "\t\t\tself.update(root, sentence, i, dp, i)\n",
    "\t\treturn dp[n]\n",
    "\t\n",
    "\tdef build(self, root, w, idx):\n",
    "\t\tif idx == len(w):\n",
    "\t\t\troot.end = True\n",
    "\t\t\treturn\n",
    "\t\tif w[idx] not in root.next:\n",
    "\t\t\troot.next[w[idx]] = TrieNode()\n",
    "\t\tself.build(root.next[w[idx]], w, idx + 1)\n",
    "\t\n",
    "\tdef update(self, root, s, idx, dp, b):\n",
    "\t\tif root.end:\n",
    "\t\t\tdp[idx] = min(dp[idx], dp[b])\n",
    "\t\tif idx == len(s):\n",
    "\t\t\treturn\n",
    "\t\tif s[idx] not in root.next:\n",
    "\t\t\treturn\n",
    "\t\tself.update(root.next[s[idx]], s, idx + 1, dp, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\r\n",
    "    def __init__(self, dic: List[str] = None) -> None:\r\n",
    "        self.child = [None] * 26\r\n",
    "        self.hasvalue = False\r\n",
    "        if dic:\r\n",
    "            for word in dic:\r\n",
    "                self.add(word)\r\n",
    "\r\n",
    "    def add(self, word: str):\r\n",
    "        node = self\r\n",
    "        for char in reversed(word):\r\n",
    "            key = ord(char) - ord(\"a\")\r\n",
    "            if not node.child[key]:\r\n",
    "                node.child[key] = Trie()\r\n",
    "            node = node.child[key]\r\n",
    "        node.hasvalue = True\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def respace(self, dictionary: List[str], sentence: str) -> int:\r\n",
    "        root = Trie(dictionary)\r\n",
    "        n = len(sentence)\r\n",
    "        dp = [0] * (n + 1)  # dp[0] = 0\r\n",
    "\r\n",
    "        for k in range(1, n + 1):\r\n",
    "            # 不尝试识别\r\n",
    "            minUnknown = dp[k - 1] + 1\r\n",
    "            # 尝试识别\r\n",
    "            node = root\r\n",
    "            i = k\r\n",
    "            while i > 0:\r\n",
    "                key = ord(sentence[i-1]) - ord(\"a\")\r\n",
    "                if node.child[key]:\r\n",
    "                    node = node.child[key]\r\n",
    "                else:\r\n",
    "                    break\r\n",
    "                if node.hasvalue:\r\n",
    "                    minUnknown = min(minUnknown, dp[i - 1])\r\n",
    "                i -= 1\r\n",
    "            # 分类讨论完毕\r\n",
    "            dp[k] = minUnknown\r\n",
    "\r\n",
    "        return dp[n]\r\n",
    "\r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
